// 多数元素

package Leetcode;

import java.util.ArrayList;
import java.util.List;

class Solution_229 {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int count1 = 0;
        int count2 = 0;
        int camp1 = 0;
        int camp2 = 0;

        for (int num : nums) {
            if (count1 == 0) { // 1阵营没人
                camp1 = num;
                count1++;
            } else if (count2 == 0) {// 2阵营没人
                camp2 = num;
                count2++;
            }
            if (count1 > 0 && num == camp1) { // 阵营1有人且当前士兵与1阵营相同
                count1++;
            } else if (count2 > 0 && num == camp2) { // 阵营2有人且当前士兵与1阵营相同
                count2++;
            } else { // 当前元素与阵营1，2都不同，则进行厮杀
                count1--;
                count2--;
            }
        }

        // 统计最后剩下的两个阵营是否大于n/3
        int cnt1 = 0;
        int cnt2 = 0;
        for (int num : nums) {
            if (num == camp1)
                cnt1++;
            if (num == camp2)
                cnt2++;
        }

        if (cnt1 > nums.length / 3)
            result.add(camp1);
        if (cnt2 > nums.length / 3 && camp1 != camp2) // 注意两者可能是相同的，需要舍去
            result.add(camp2);
        return result;
    }
}